Em Complexidade computacional, PP é a classe de problemas de decisão decidíveis por uma Máquina de Turing probabilística em tempo polinomial, com uma probabilidade de erro de menos do que 1/2 para todas as instâncias. A abreviação PP se refere a tempo polinomial probabilístico. A classe de complexidade foi definida por Gill em 1977.

Se um problema de decisão está em PP, então existe um algoritmo para ele que se permite "jogar moedas para cima" e tomar decisões aleatórias. É garantido que ele rode em tempo polinomial. Se a resposta é SIM, o algoritmo vai responder SIM com uma probabilidade maior do que 1/2. Se a resposta for NÃO, o algoritmo vai responder SIM com uma probabilidade menor ou igual a 1/2. Em termos mais práticos, ela é a classe dos problemas que podem ser decididos para qualquer grau de precisão fixo rodando um algoritmo de tempo polinomial aleatoriamente por um número de vezes suficientes (mas limitado).

Uma caracterização alternativa para PP é o conjunto de problemas que pode ser resolvido por uma Máquina de Turing não determinística em tempo polinomial onde a condição de aceitação é que a maioria (mais da metade) dos caminhos de computação são aceitos. Por causa disso, alguns autores sugerem o nome alternativo Majority-P